1. Field of the Invention
The present invention relates to a design of scalable techniques for Quality of Services (QoS) routing and forwarding. More particularly, the present invention relates to a use of a design of scalable techniques for QoS routing and forwarding.
2. Description of the Related Art
The next generation of the Internet must provide users with diverse, fine-grain, and subjective QoS functions, particularly in light of the increasing demand for a wide spectrum of network services. Even though Resource ReSerVation Protocol (RSVP) can reserve resources for individual flows (that is, an IP packet stream between the same source-destination (S-D) pair of the session), however, current Routing Information Protocol (RIP) and the Open Shortest Path First (OSPF) protocol always find the shortest paths, and do not consider the bandwidth or other the limitations of the link. Consequently, the path may not have enough resources to provide the QoS for the flow request. In this way, RSVP reservation from the receiver could be blocked. That is, RSVP can work with RIP or OSPF to provide QoS to individual flows, however, probably with a substantially high blocking probability. Also, whenever the per-destination entry of the routing table is updated, the next hop of the associated route may be changed immediately, possibly interrupting the QoS of the flow forwarded on that path.
To reduce the blocking probability and keep stable provision during the session of a flow, QoS routing is highly desired in integrated services networks. QOSPF routing mechanism of the IETF is QoS extensions to the current OSPF, thus providing QoS path computation. During computation, QOSPF takes link bandwidth into account and the results are stored on the QoS routing table, and is used to lookup the path of a new flow request (e.g., new PATH messages of RSVP).
Moreover, for route pinning, routers can avoid oscillation and facilitate wire-speed forwarding of packets by using a forwarding cache, to record the forwarding decisions. In this way, routers usually do not need to query the QoS routing table upon packet arrival. In addition, the cache pins the forwarding path to avoid frequent change(s) which may interrupt the QoS provision.
Among the factors that affect the QoS routing performance and efficiency, granularity of the routing decision significantly affects the scalability and the blocking probability. In present day, different routing techniques use different granularities. For example, OSPF has the coarsest granularity and uses per-destination routing entries. As a request, all flows moving from different sources to a destination are forwarded to the same outgoing link on the same router. Moreover, routing granularity of MOSPF and a version of QOSPF are per-pair, i.e. based on source and the destination addresses of routed flows. In that way, all traffics of a given source and a given destination, regardless of the number of flows, travels the same route. Among the other QoS routing algorithms, such as PQC and alternate path routing, have the finest granularity, i.e per-flow. Each individual flow is routed independently.
Per-pair cache entries could result in misleading, i.e., flows following a cache entry might not find sufficient resources along the path while other paths with abundant resources still exist. This lack of resources is attributed to that flows of the same node pair use the same entry computed merely for the first existing flow between the node pair. Therefore, this path might not satisfy the bandwidth requirements of subsequent flows. Notably, the blocking probability increases when a link along the path becomes a bottleneck. On the other hand, although no such misleading occurs in the per-flow routing the cache size could be enormous. Poor scalability would ultimately result. Furthermore, due to the overhead of per-flow path computation, on-demand path-finding is hardly feasible in real networks. Therefore, path pre-computation is implemented in a version of QOSPF, which provides the results of computational cost and protocol overhead in QoS routing. In sum, QOSPF has the strength in low blocking probability and scalability in path computation. However, in wire-speed forwarding routers, per-flow forwarding of QOSPF loses storage scalability, from the perspective of the size of the forwarding cache.
The invention provides three scalable techniques for QoS routing and forwarding: 1) Overflowed cache technique-the mechanism provides three different granularities within the routing/forwarding cache. 2) Per-class routing mark techniquexe2x80x94the mechanism computes several alternate routes between each source-destination (S-D) pair. 3) Two-phase routing techniquexe2x80x94this mechanism provides a soft-reservation concept in order to reduce the misleading probability in the per-pair routing/forwarding cache. Hence, these QoS routing techniques not only routes data flows with quality of services (QoS), but also fast forwards data packets, reduces the blocking probability, and achieves storage and computational scalability.
As embodied and broadly described herein, the invention provides a design for a Quality of Services routing and forwarding with scalability, which includes three techniques: overflowed cache, per-class routing mark and two-phase routing, wherein the three techniques can be simultaneous or individual implemented.
The cache of the overflowed cache technique can be divided into three parts: a per-pair P-Cache, a per-flow O-Cache, and a per-destination D-Cache. When a data or control packet arrives a QoS router, the process in which the packet is forwarded, can be detailed as the following steps:
1. First, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;
2. If the packet is a control packet, forwards it to the control module to process and update the flow state database (FSDB), refresh the flow state if the packet belongs to existing flows. Otherwise, the P-Cache and the residual bandwidth database (RBDB) are examined;
3. If it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and
4. If it is a QoS data packet, the O-Cache, the P-Cache and the D-Cache are simultaneously looked up. The packet is forwarded to the next hop router according to the O-Cache entry if the O-Cache lookup is a hit. Otherwise, the packet is forwarded according to the P-Cache entry if the P-Cache lookup is a hit. If both lookups are misses, the packet is forwarded according to the D-Cache entry.
The above-described examines the P-Cache and the RBDB must perform the following steps:
1. Source-destination addresses of the packet are used to lookup the P-Cache entries;
2. If the P-Cache lookup is a hit, then a request bandwidth b is checked with the RBDB to ensure the QoS of the new flow. If the check is successful, then the bandwidth is temporarily reserved for the new flow, and the flow will be forwarded according to the path on the P-Cache entry. On the other hand, if RBDB indicates that the residual bandwidth is not enough, the path computation function is invoked to find a QoS path based on the information in LSDB and RBDB. If a QoS path v is found, the forwarding information of this new flow is stored in the O-cache, i.e. overflowed to the O-cache. If no path can be found, the flow is blocked;
3. If the P-Cache lookup is a miss, this implies that no forwarding information is stored for the new flow. Therefore, the routing algorithm attempts to compute a QoS path. If the path "sgr" is found, the algorithm stores the forwarding information in the P-cache. Otherwise, it blocks the flow.
As for the per-class routing mark technique, its implementation is as follows:
1. First, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;
2. If it is a control packet, forwards it to the control module to process and update the flow state database (FSDB). Note that in case of edge router and the flow is a new request, the C-Cache (i.e. O-Cache and P-Cache combination) and the residual bandwidth database (RBDB) are examined. That is, the algorithm uses the source-destination addresses of the control packet to extract the least costly
feasible path xcfx80 and the index of sub-entry m from the C-Cache. According to the number of sub-entries of the desired S-D pair, three cases will be further discussed;
3. If it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and
4. If it is a QoS data packet, indexing the S-D address pair and routing mark simultaneously look up the C-Cache and the D-Cache. The packet is forwarded to the next hop router according to the C-Cache entry if the C-Cache lookup is a hit. Otherwise, the packet is forwarded according to the D-Cache entry. Note that in case of edge router, the routing mark must be retrieved from the flow state database and insert it into the packet header, then forwards the packet to the next hop router.
The three above-described cases are:
1. If the number of sub-entries of the desired S-D pair in C-Cache is xe2x80x98emptyxe2x80x99, the lookup will be missed and the algorithm attempts to compute the least costly feasible path, termed "sgr". If "sgr" is found, the algorithm assigns a new mark to "sgr", inserts it into the C-Cache, and then updates the flow state database. If "sgr" is not found, the flow is blocked;
2. If the number of sub-entries of the desired S-D pair in C-Cache is xe2x80x98fullxe2x80x99, this algorithm simply finds the least costly feasible path n among the existing Π(s, d) paths, where xcfx80xcex5xcex5Π(s, d). If xcfx80 is found, the flow will be marked with the index of xcfx80, and thus update the flow state database. If xcfx80 is not found, then blocks the flow; and
3. If the number of sub-entries of the desired S-D, Π(s, d), is neither empty nor full, this algorithm can either route the flow through the xcfx80 led by the C-Cache as in case 2, or route the flow through a newly computed path "sgr" as in case 1, whichever costs less. Note that no matter which is chosen, the flow state database is updated with the desired routing mark.
Furthermore, the path computation module may use a two-phase routing technique. When a data or control packet arrives a QoS router, the process in which the packet is forwarded, can be detailed as the following steps:
1. First, when the packet arrives at a router, the source-destination IP addresses, source-destination port numbers and protocol identification in the packet header are used to distinguish data packet and control packet;
2. If the packet is a control packet, forwards it to the control module to process and update the flow state database (FSDB), refresh the flow state if the packet belongs to existing flows. Otherwise, use the S-D pair addresses to lookup the P-Cache and the residual bandwidth database (RBDB) is examined.
3. If it is a best effort data packet, forwards it to the next-hop router by looking up the per-destination D-Cache whose shortest paths entries are pre-computed; and
4. If it is a QoS data packet, the P-Cache and the D-Cache are simultaneously looked up. The packet is forwarded to the next hop router according to the P-Cache entry if the P-Cache lookup is a hit. Otherwise, the packet is forwarded according to the D-Cache entry.
Use of the S-D address pair to lookup the P-Cache includes implementing the following steps:.
1. If the P-Cache lookup is a hit, and the feasibility check with RBDB is successful (i.e., with enough residual bandwidth), then the flow will be forwarded through the path led by the P-Cache. If there is not enough residual bandwidth, then the flow is blocked;
2. If the P-Cache lookup is a miss, this implies that no forwarding information is stored for the new flow. Therefore, the two-phase routing technique is used to compute a feasible QoS path. If the path "sgr" is found, the algorithm stores the forwarding information in the P-cache. Otherwise, it blocks the flow.
Moreover, the path computation module is based on the following two-phase computation:
1. Phase-I, referred to as soft-reservation, tries to find a path "sgr"1 with greater bandwidth than the request b, i.e. where width("sgr"1)xe2x89xa7b+bmore. The bmore value can be roughly estimated and can be adjusted according to the traffic volume. Path information of "sgr"1 is inserted into the P-Cache, and the soft-residual bandwidth is recorded into the soft-RBDB database. Consequently, the subsequent incoming flows of the same S-D pair will be more likely to successfully reserve bandwidth on the minimum-hop path "sgr"1. Less misleading will increase the likelihood of success; and
2. If a QoS path "sgr"1 cannot be found, Phase-II will attempt to compute a path "sgr"2 with bandwidth b, i.e., width("sgr"2)xe2x89xa7b, referred to as hard-reservation because it considers the actual required bandwidth. Path information of "sgr"2 is inserted into the P-Cache, and the hard-residual bandwidth is recorded into the hard-RBDB database. If QoS path "sgr"2 cannot be computed, the flow is blocked.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, and are intended to provide further explanation of the invention as claimed.